"""
https://leetcode.cn/problems/relative-sort-array/description/

1122. 数组的相对排序
简单
相关标签
相关企业
提示
给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

 

示例 1：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
示例  2:

输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出：[22,28,8,6,17,44]
 

提示：

1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i]  各不相同 
arr2 中的每个元素 arr2[i] 都出现在 arr1 中
"""

from typing import Dict, List


class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        """
        将arr2做成一个hash表，然后重写compare方法
        """

        map:Dict[int,int] ={}
        for i,v in enumerate(arr2):
            map[v]=i

        def compare_sort(v1:int,v2:int)->int:
            if v1==v2:
                return 0
            if v1 in map and v2 in map:
                i1=map[v1]
                i2=map[v2]
                if i1<i2:
                    return -1
                else:
                    return 1
            if v1 in map:
                return -1
            if v2 in map:
                return 1
            if v1<v2:
                return -1
            else:
                return 1

        def merge(lr:List[int],rr:List[int])->List[int]:
            res=[]
            i1=i2=0
            while i1<len(lr) and i2<len(rr):
                if compare_sort(lr[i1],rr[i2])<=0:
                    res.append(lr[i1])
                    i1+=1
                else:
                    res.append(rr[i2])
                    i2+=1
            while i1<len(lr):
                res.append(lr[i1])
                i1+=1
            while i2<len(rr):
                res.append(rr[i2])
                i2+=1
            return res

        def merge_sort(nums:List[int],left:int,right:int)->List[int]:
            """
            左闭右开
            """
            if left+1==right:
                return [nums[left]]
            mid=(left+right)//2
            left_res=merge_sort(nums,left,mid)
            right_res=merge_sort(nums,mid,right)
            return merge(left_res,right_res)

        return merge_sort(arr1,0,len(arr1))


if __name__=='__main__':
    sol=Solution()
    arr1=[2,3,1,3,2,4,6,7,9,2,19]
    arr2=[2,1,4,3,9,6]

    res=sol.relativeSortArray(arr1,arr2)
    print(res)

    pass